﻿using System;
using System.Collections.Generic;
using System.Threading;
using Jiubang.Tracer;
using log4net;

namespace Jiubang.Collections {
    /// <summary>
    /// 基于LFU淘汰算法Dictionary缓存结构。
    /// 比基于链表的LRU优势在于读取的性能。读取只是对计算器原子自增。
    /// 作为替代，回收内存的成本较高。因此采用批量回收的机制减少性能开销。
    /// 淘汰成本随容量递增。容量较大时应考虑使用LinkedHashMap以获得较稳定的性能。
    /// 该类线程安全。
    /// </summary>
    public class CounterDict<TKey, TValue> {
        private readonly bool _allowDefaultValueStoring;
        private readonly Dictionary<TKey, Entry> _dict;
        private readonly DateTime _initialTime = DateTime.Now;
        private readonly ILog _log;

        #region 私有字段
        private int capacity;
        private int gets;
        private int misses;
        private string name;
        private IList<KeyValuePair<TKey, TValue>> recycleList;
        private int recyclingQuantity;
        private Dictionary<TKey, Entry> writeBuffer, readBuffer;
        private DateTime nextRecyclingTime = DateTime.Now;
        private TimeSpan minRecyclingInterval = TimeSpan.FromMinutes(3);
        private readonly NoEqualComparer<int> notEqualComparer = new NoEqualComparer<int>(null);

        #endregion

        #region 构造函数
        /// <param name="capacity">初始容量</param>
        /// <param name="comparer">键比较器</param>
        public CounterDict(int capacity, IEqualityComparer<TKey> comparer) : this(capacity, comparer, false) { }

        /// <param name="capacity">初始容量</param>
        /// <param name="comparer">键比较器</param>
        /// <param name="allowDefaultValueStoring">允许存储默认值。默认设置为不保存，连续请求该键则每次均尝试调用回调方法</param>
        public CounterDict(int capacity, IEqualityComparer<TKey> comparer, bool allowDefaultValueStoring) {
            var type = GetType();
            _log = LogManager.GetLogger(type);
            name = type.Name;

            _dict = new Dictionary<TKey, Entry>(capacity, comparer);
            Capacity = capacity;
            RecyclingQuantity = capacity / 10;
            this._allowDefaultValueStoring = allowDefaultValueStoring;
        }

        /// <param name="capacity">初始容量</param>
        public CounterDict(int capacity) : this(capacity, EqualityComparer<TKey>.Default) { }
        #endregion

        #region 回调函数
        /// <summary>
        /// 缓存未命中的回调
        /// </summary>
        public CacheItemMissedCallback<TKey, TValue> CacheMissedHandler { get; set; }

        /// <summary>
        /// 缓存超过容量而被回收后的回调
        /// </summary>
        public CacheItemsRecycledCallback<TKey, TValue> CacheItemsRecycledHandler { get; set; }
        #endregion

        /// <summary>
        /// 设置或获取缓存的容量（不少于10）
        /// </summary>
        public int Capacity {
            get { return capacity; }
            set {
                if (value < 10) {
                    throw new ArgumentOutOfRangeException("value", "缓存的容量应该不少于10");
                }
                capacity = value;
            }
        }

        /// <summary>
        /// 名称。用于跟踪时的标识。
        /// </summary>
        public string Name {
            get { return name; }
            set {
                if (value == null) throw new ArgumentNullException();
                name = value;
            }
        }

        /// <summary>
        /// 每次执行内存回收的移除的项数量
        /// </summary>
        public int RecyclingQuantity {
            get { return recyclingQuantity; }
            set {
                if (value < 1 || value > capacity / 2) {
                    throw new ArgumentOutOfRangeException("value", "每次回收项数应介于1至容量的一半之间");
                }
                recyclingQuantity = value;
            }
        }

        /// <summary>
        /// 获取或设置一个缓存项。
        /// CacheMissedHandler未设置时，获取一个不存在的项将引发异常。
        /// 获取时如CacheMissedHandler回调返回Null，该项不加入缓存。
        /// </summary>
        /// <param name="key"></param>
        /// <exception cref="KeyNotFoundException" />
        /// <returns></returns>
        public TValue this[TKey key] {
            get {
                Entry entry;
                if (TryGetEntry(key, out entry)) {
                    return entry.Value;
                }

                if (CacheMissedHandler != null) {
                    var value = CacheMissedHandler(key);
                    if (_allowDefaultValueStoring || !Equals(value, default(TValue))) {
                        this[key] = value;
                    }
                    return value;
                }
                throw new KeyNotFoundException();
            }
            set {
                //新设置的值不在第一次被回收
                var entry = new Entry { Value = value, Counter = 0 };
                DateTime now = DateTime.Now;
                lock (_dict) {
                    //是否处于淘汰作业
                    if (recycleList == null) {
                        //非淘汰作业下，容量超过上限
                        if (_dict.Count >= Capacity && now > nextRecyclingTime) {
                            nextRecyclingTime = now.Add(minRecyclingInterval);
                            //遍历，必须保持同步状态
                            recycleList = GetRecycleList();
                            ThreadPool.QueueUserWorkItem(Recycle);
                        } else {
                            //插入缓存项
                            _dict[key] = entry;
                            return;
                        }
                    }

                    //淘汰作业状态先加入缓冲表
                    if (writeBuffer == null) {
                        writeBuffer = new Dictionary<TKey, Entry>(Capacity / 10);
                    }
                    writeBuffer[key] = entry;
                }
            }
        }

        /// <summary>
        /// 当前容器的数据请求次数
        /// </summary>
        public int Gets {
            get { return gets; }
        }

        /// <summary>
        /// 缓存未命中的次数
        /// </summary>
        public int Misses {
            get { return misses; }
        }

        /// <summary>
        /// 容器的运行时间（秒）
        /// </summary>
        public double Uptime {
            get { return (DateTime.Now - _initialTime).TotalSeconds; }
        }

        /// <summary>
        /// 设置或获取回收器执行的最短间隔。
        /// 下限为3秒，上限为30分钟，默认为3分钟。
        /// 该值影响LFU取样范围，不建议过低。
        /// 在回收器最短执行间隔范围内，缓存总量可能超过上限。
        /// </summary>
        public TimeSpan MinRecyclingInterval {
            get { return minRecyclingInterval; }
            set {
                if (value < TimeSpan.FromSeconds(3) || value > TimeSpan.FromMinutes(30))
                    throw new ArgumentOutOfRangeException("value", "下限为3秒钟，上限为30分钟");
                minRecyclingInterval = value;
            }
        }

        /// <summary>
        /// 目前只在主缓存中查找是否存在指定键
        /// </summary>
        public bool ContainsKey(TKey key) {
            return _dict.ContainsKey(key);
        }

        /// <summary>
        /// 异步执行多余空间回收操作
        /// </summary>
        /// <param name="state"></param>
        private void Recycle(object state) {
            if (recycleList.Count > 2 * recyclingQuantity) {
                _log.WarnFormat("待回收清单长度为{0}，超出期望值{1}两倍以上。如本消息持续出现，建议增加缓存容量。", recycleList.Count, recyclingQuantity);
            } else if (_log.IsDebugEnabled) {
                _log.DebugFormat("计划回收{0}项，当前缓存大小为{1}，设置回收大小为{2}", recycleList.Count, _dict.Count, recyclingQuantity);
            }

            try {
                var tracer = TraceManager.GetTracer(Name);
                try {
                    //对待回收项预处理，用于取消移除列表中的任意项的执行。
                    //可能存在低性能操作，不应在同步任务中执行。
                    if (CacheItemsRecycledHandler != null) {
                        CacheItemsRecycledHandler(recycleList);
                    }

                    //从缓存容器中移除
                    //所有对recycleList的写操作都在dict锁下进行，不需要考虑线程问题
                    foreach (var keyValuePair in recycleList) {
                        lock (_dict) {
                            _dict.Remove(keyValuePair.Key);
                        }
                    }
                } finally {
                    tracer.Check(() => "空间回收完成", 100);
                    tracer.Dispose();
                }
            } catch (Exception e) {
                _log.Error(e);
            } finally {
                //write创建与更新皆由dict锁控制，读取算法线程安全
                lock (_dict) {
                    //使遍历期间仍然可以访问缓冲区数据
                    readBuffer = writeBuffer;
                    writeBuffer = null;
                    recycleList = null;
                }
            }

            //缓冲数据回写
            if (readBuffer != null) {
                try {
                    foreach (var keyValuePair in readBuffer) {
                        lock (_dict) {
                            _dict[keyValuePair.Key] = keyValuePair.Value;
                        }
                    }
                    if (_log.IsDebugEnabled) {
                        _log.DebugFormat("数据回写{0}项，当前缓存大小为{1}/{2}，设置回收大小{3}", readBuffer.Count, _dict.Count, capacity, recyclingQuantity);
                    }
                } catch (Exception e) {
                    _log.Error(e);
                } finally {
                    readBuffer = null;
                }
            }
        }


        private bool TryGetEntry(TKey key, out Entry entry) {
            Interlocked.Increment(ref gets);
            if (_dict.TryGetValue(key, out entry)) {
                return true;
            }
            Interlocked.Increment(ref misses);
            //主缓存未命中时，查询缓存表
            var buffer = writeBuffer??readBuffer;
            return buffer != null && buffer.TryGetValue(key, out entry);
        }

        /// <summary>
        /// 尝试获取一个缓存项，不调用CacheMissedHandler回调
        /// </summary>
        /// <param name="key"></param>
        /// <param name="value"></param>
        /// <returns></returns>
        public bool TryGetValue(TKey key, out TValue value) {
            Entry entry;
            if (TryGetEntry(key, out entry)) {
                value = entry.Value;
                return true;
            }
            value = default(TValue);
            return false;
        }

        /// <summary>
        /// 从缓存中移除一个项
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public bool Remove(TKey key) {
            lock (_dict) {
                //tempDict的字段的更新由dict锁控制
                var removed = false;
                if (writeBuffer != null)
                    removed = writeBuffer.Remove(key);
                //不能一句解决，||操作在前项判断为true将略过后项判断
                return _dict.Remove(key) || removed;
            }
        }

        /// <summary>
        /// 获取要移除的项
        /// </summary>
        /// <returns></returns>
        private IList<KeyValuePair<TKey, TValue>> GetRecycleList() {
            //移除的目标设置为剩余RecycleQuantity。
            var expectSize = _dict.Count - capacity + recyclingQuantity;
            if (expectSize <= 0) {
                _log.WarnFormat("计划回收空间为{0}。当前缓存大小{1}/{2}，设置回收大小{3}", expectSize, _dict.Count, capacity, recyclingQuantity);
            }

            var list = new SortedList<int, KeyValuePair<TKey, TValue>>(expectSize, notEqualComparer);
            foreach (var pair in _dict) {
                var counter = pair.Value.Counter;
                //重置计数器
                pair.Value.Counter = int.MinValue;
                //回收列表未满时添加
                if (list.Count < list.Capacity) {
                    list.Add(counter, new KeyValuePair<TKey, TValue>(pair.Key, pair.Value.Value));
                    continue;
                }
                //当前计数大于回收列表时跳过
                var lastIndex = list.Count - 1;
                if (counter >= list.Keys[lastIndex]) {
                    continue;
                }

                //将当前项加入列表替换最后一项
                list.RemoveAt(lastIndex);
                list.Add(counter, new KeyValuePair<TKey, TValue>(pair.Key, pair.Value.Value));
            }
            return list.Values;
        }

        #region Nested type: Entry

        private class Entry {
            private int counter;
            private TValue value;

            public TValue Value {
                get {
                    Interlocked.Increment(ref counter);
                    return value;
                }
                set { this.value = value; }
            }

            public int Counter {
                get { return counter; }
                set { counter = value; }
            }
        }

        #endregion
    }
}